/*
 * @lc app=leetcode.cn id=748 lang=typescript
 *
 * [748] 最短补全词
 */

// @lc code=start
function shortestCompletingWord(licensePlate: string, words: string[]): string {
  const hash = new Map<string, number>();
  // 将所有的字母放入hash表中
  const chars = licensePlate
    .toLocaleLowerCase()
    .split('')
    .filter((c) => /[a-z]/.test(c));
  // 统计licensePlate中的字符出现次数
  for (const c of chars) {
    hash.set(c, (hash.get(c) || 0) + 1);
  }

  let minLen = Number.POSITIVE_INFINITY;
  let ans = '';

  for (const word of words) {
    // 复制一份hash用作当前word比较
    const map = new Map(hash);
    // 利用当前word中的char去更新哈希表
    // 出现过的char数量减少1
    // 如果出现过的char数量为0，则移除该char
    for (const char of word) {
      if (map.has(char)) {
        map.set(char, map.get(char) - 1);
        if (map.get(char) === 0) map.delete(char);
      }
    }
    // 如果当前word中的字符出现次数和licensePlate中的字符出现次数相同或者更多，则更新最短长度和最短词
    if (map.size === 0) {
      if (minLen > word.length) {
        minLen = word.length;
        ans = word;
      }
    }
  }

  return ans;
}
// @lc code=end
